/*
 * @lc app=leetcode.cn id=480 lang=javascript
 *
 * [480] 滑动窗口中位数
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var medianSlidingWindow = function (nums, k) {
  // 对顶堆
  const small = new MaxPQ();
  const big = new MinPQ();
  // 延迟删除的数据
  const delNums = {};

  //将k个数据放入优先队列中
  for (let i = 0; i < k; i++) {
    small.insert(nums[i]);
  }
  for (let i = 0; i < Math.floor(k / 2); i++) {
    big.insert(small.delTop());
  }

  const result = [getMedian()];
  for (let i = k; i < nums.length; i++) {
    // 记录需要延迟删除的数字
    const delIdx = nums[i - k];
    delNums[delIdx] = delNums[delIdx] ? delNums[delIdx]++ : 1;
    let balance = 0;
    // 记录状态，保持2个堆的平衡
    if (!small.isEmpty() && delIdx <= small.top()) {
      balance--;
    } else {
      balance++;
    }
    if (small.isEmpty() || nums[i] <= small.top()) {
      small.insert(nums[i]);
      balance++;
    } else {
      big.insert(nums[i]);
      balance--;
    }
    if (balance > 0) {
      big.insert(small.delTop());
    }
    if (balance < 0) {
      small.insert(big.delTop());
    }
    while (!small.isEmpty() && delNums[small.top()] > 0) {
      delNums[small.delTop()]--;
    }
    while (!big.isEmpty() && delNums[big.top()] > 0) {
      delNums[big.delTop()]--;
    }

    result.push(getMedian());
  }

  return result;

  function getMedian() {
    return k % 2 !== 0 ? small.top() : (small.top() + big.top()) / 2;
  }
};

class MaxPQ {
  constructor() {
    this.pq = [];
    this.size = 0;
  }
  isEmpty() {
    return this.size === 0;
  }
  less(i, j) {
    return this.pq[i] < this.pq[j];
  }
  exch(i, j) {
    [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
  }
  swin(k) {
    while (k > 0 && this.less(Math.floor((k - 1) / 2), k)) {
      this.exch(k, Math.floor((k - 1) / 2));
      k = Math.floor((k - 1) / 2);
    }
  }
  sink(k) {
    while (2 * k + 1 < this.size) {
      let j = 2 * k + 1;
      if (j < this.size && this.less(j, j + 1)) {
        j++;
      }
      if (this.less(j, k)) {
        return;
      }
      this.exch(k, j);
      k = j;
    }
  }
  insert(v) {
    this.pq.push(v);
    this.swin(this.size);
    this.size++;
  }
  top() {
    return this.pq[0];
  }
  delTop() {
    let top = this.pq[0];
    this.exch(0, this.size - 1);
    this.pq.pop();
    this.size--;
    this.sink(0);
    return top;
  }
}

class MinPQ {
  constructor() {
    this.pq = [];
    this.size = 0;
  }
  isEmpty() {
    return this.size === 0;
  }
  less(i, j) {
    return this.pq[i] < this.pq[j];
  }
  exch(i, j) {
    [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
  }
  swin(k) {
    while (k > 0 && this.less(k, Math.floor((k - 1) / 2))) {
      this.exch(k, Math.floor((k - 1) / 2));
      k = Math.floor((k - 1) / 2);
    }
  }
  sink(k) {
    while (2 * k + 1 < this.size) {
      let j = 2 * k + 1;
      if (j < this.size && this.less(j + 1, j)) {
        j++;
      }
      if (this.less(k, j)) {
        return;
      }
      this.exch(k, j);
      k = j;
    }
  }
  insert(v) {
    this.pq.push(v);
    this.swin(this.size);
    this.size++;
  }
  top() {
    return this.pq[0];
  }
  delTop() {
    let top = this.pq[0];
    this.exch(0, this.size - 1);
    this.pq.pop();
    this.size--;
    this.sink(0);
    return top;
  }
}
// @lc code=end
medianSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3);
